#include "quickSort.h"
#include "util.h"

void quickSort(int* array, int length){
    //srand(time(NULL));
    __quickSort(array, 0 , length-1);
}

//优化可以使用三向切分进行优化
static void __quickSort(int* array,int left,int right){
    //小数组使用插入排序进行优化
    if(left >= right){
        return;
    }
    int p = __partition(array,left,right);
    __quickSort(array,left,p-1);
    __quickSort(array,p+1,right);
}


//可以使用
static int __partition(int* array,int left,int right){
    //swap(&array[left],&array[rand()%(right-left+1)+left]);
    int v = array[left];
    int j = left;
    int k;
    for (k = left+1; k <= right ; k++) {
        if(array[k] < v){
            swap(&array[j+1],&array[k]);
            j++;
        }
    }
    swap(&array[left],&array[j]);
    return j;
}
